home *** CD-ROM | disk | FTP | other *** search
/ SPACE 1 / SPACE - Library 1 - Volume 1.iso / program / 70 / examples / examples.arc / TURING.ST < prev    next >
Text File  |  1985-11-20  |  3KB  |  125 lines
  1. "
  2.     Turing machine simulator contributed by Jan Gray,
  3.         the University of Waterloo
  4. "
  5. Class Main
  6. [
  7.     main            | tm |
  8.         tm <- TuringMachine new initialize.
  9.         tm delta state: 0 input: $# nextState: 1 output: $L.
  10.         tm delta state: 1 input: $I nextState: 1 output: $i.
  11.         tm delta state: 1 input: $i nextState: 1 output: $L.
  12.         tm delta state: 1 input: $# nextState: 2 output: $R.
  13.         tm delta state: 2 input: $i nextState: 2 output: $R.
  14.         tm delta state: 2 input: $# nextState: 'halt' output: $#.
  15.         tm tape: 'IIIIII'.
  16.         tm delta print.
  17.         tm run
  18. ]
  19. Class TuringMachine
  20. |    tape        "Infinite tape"
  21.     state        "Current state, TM continues if state is a number"
  22.     delta        "A TransitionTable, which for each (state, input)
  23.              gives (next state, output)"
  24.     tapeMoves    "A Dictionary which maps L and R into [tape left]
  25.              and [tape right]"
  26. |
  27. [
  28.     initialize
  29.         tapeMoves <- Dictionary new.
  30.         tapeMoves at: $L put: [tape left].
  31.         tapeMoves at: $R put: [tape right].
  32.         delta <- TransitionTable new.
  33.         self tape: ''.
  34.         self state: 0
  35. |
  36.     tape: aString
  37.         tape <- Tape new with: aString
  38. |
  39.     state: aState
  40.         state <- aState
  41. |
  42.     delta
  43.         ^ delta
  44. |
  45.     step
  46.         | next |
  47.         next <- delta atState: state input: tape read.
  48.         state <- next state.
  49.         (state isKindOf: Number)
  50.             ifTrue: [(tapeMoves includesKey: next symbol)
  51.                 ifTrue:    [(tapeMoves at: next symbol) value]
  52.                     ifFalse: [tape write: next symbol]]
  53. |
  54.     run
  55.         state <- 0.
  56.         self print.
  57.         [state isKindOf: Number] whileTrue: [self step print]
  58. |
  59.     printString
  60.         ^ 'State ', state printString, ', Tape ', tape printString
  61. ]
  62. Class Pair    :Magnitude
  63. | state symbol |
  64. [
  65.     state: aState symbol: aSymbol
  66.         state <- aState.
  67.         symbol <- aSymbol
  68. |
  69.     state
  70.         ^ state
  71. |
  72.     symbol
  73.         ^ symbol
  74. |
  75.     < aPair
  76.         ^ state < aPair state or:
  77.             [state = aPair state and: [symbol < aPair symbol]]
  78. |
  79.     printString
  80.         ^ state printString, '    ', symbol printString
  81. ]
  82. Class TransitionTable :Dictionary
  83. [
  84.     state: aState input: in nextState: nextState output: out
  85.         self at: (Pair new state: aState symbol: in)
  86.             put: (Pair new state: nextState symbol: out).
  87.         ^ nil
  88. |
  89.     atState: aState input: in
  90.         ^ self at: (Pair new state: aState symbol: in)
  91.             ifAbsent: [^ Pair new state: 'hung' symbol: nil].
  92. |
  93.     print
  94.         'State    Read    Next    Write' print.
  95.         self binaryDo: [:x :y |
  96.             (x printString , '    ', y printString) print]
  97. ]
  98. Class Tape :Object
  99. | tape position |
  100. [
  101.     with: aString
  102.         tape <- '#', aString, '#'.
  103.         position <- tape size
  104. |
  105.     read
  106.         ^ tape at: position
  107. |
  108.     write: aChar
  109.         tape at: position put: aChar.
  110. |
  111.     left
  112.         (position > 1)
  113.             ifTrue: [position <- position - 1]
  114. |
  115.     right
  116.         (position = tape size)
  117.             ifTrue: [tape <- tape, '#'].
  118.         position <- position + 1
  119. |
  120.     printString
  121.         ^ (tape copyFrom: 1 to: position - 1), '{',
  122.             ((tape at: position) asString), '}',
  123.             (tape copyFrom: position + 1 to: tape size)
  124. ]
  125.